\documentclass{ctexart}
\usepackage{standalone}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{tikz}
\usepackage{listings}
\usepackage{amssymb}

\begin{document}

\title{硬币找零问题}
\author{金郁香}
\date{\today}

\maketitle

\section{项目概述}
本项目是一个用于解决硬币找零问题的程序。给定目标金额和每种硬币的数量，程序将计算出最少需要多少枚硬币才能组成目标金额。

\section{文件结构}
本项目包含以下文件：
\begin{itemize}
  \item \texttt{main.cpp}：包含主函数，用于接收用户输入并调用算法函数进行计算。
  \item \texttt{coin.h}：定义了硬币找零问题的函数原型，并实现了硬币找零问题的算法。
  \item \texttt{Makefile}：用于自动编译和构建项目。
  \item \texttt{report.tex}：用于生成项目报告的 LaTeX 源文件。
\end{itemize}

\section{算法说明}
本项目使用动态规划算法来解决硬币找零问题。具体实现如下：
\begin{itemize}
  \item 定义一个二维数组 \texttt{dp}，其中 \texttt{dp[i][0]} 表示使用这 \texttt{j} 种硬币组成总金额 \texttt{i} 所需的最小硬币数，\texttt{dp[i][j]} 表示此时第 \texttt{j} 种硬币的使用数量。
  \item 初始化 \texttt{dp} 数组为 \texttt{amount+1}，表示初始情况下不可能组成总金额 \texttt{i}。
  \item 对于每个金额 \texttt{i}，遍历每种硬币 \texttt{coin[j-1]}，如果当前硬币面额 \texttt{coin[j-1]} 小于等于当前金额 \texttt{i} 并且使用 \texttt{coin[j-1]} 硬币后该硬币的使用数量不超过该硬币总数（即 \texttt{dp[i][j]<=a[j-1]}），那么将 \texttt{dp[i-coin[j]][0]} 的值加上 1 与 \texttt{dp[i][0]} 进行比较，取较小值更新 \texttt{dp[i][0]},同时更新当前金额 \texttt{i} 下各种硬币的使用数量。
  \item 最后，返回 \texttt{dp[amount][0]} 即可得到总金额为 \texttt{amount} 时的最小硬币数。
\end{itemize}

\section{算法时间复杂度和效率}
动态规划算法的时间复杂度为 $O(n \cdot m)$，其中 $n$ 是目标金额，$m$ 是硬币的种类数。在本算法中，我们需要计算出 $dp$ 数组的所有元素，因此需要进行 $n \cdot m$ 次操作。

由于动态规划算法的特性，我们可以通过在迭代过程中逐步构建 $dp$ 数组，避免不必要的重复计算，从而提高算法的效率。


\section{编译和运行}
在终端中进入项目目录，并执行以下命令来编译和运行程序：
\begin{verbatim}
make
./test
然后依次输入总金额及四种硬币的数量，按回车运行。
\end{verbatim}

\section{测试说明}
本项目包含以下测试用例：
\begin{enumerate}
  \item 输入：\texttt{n = 2314}，\texttt{a = \{50, 50, 50, 50\}} \\
        预期输出：fail to change \\
        解释：无法使用给定的硬币数量组成2314美分。
  \item 输入：\texttt{n = 1314}，\texttt{a = \{50, 50, 50, 50\}} \\
        预期输出：60 \\
        解释：可以使用50个25美分、6个10美分、4个1美分硬币组成1314美分。
  \item 输入：\texttt{n = 1023489}，\texttt{a = \{100000,100000,100000,100000\}} \\
        预期输出：40944 \\
        解释：不解释啦(这么小的币值对这么大的金额找零已经有点离谱了～)。
        
经测试发现，算法的实际运行时间与理论分析相符合，能够在较短时间内得到正确的输出。\\
        
\end{enumerate}

\section{总结}
本项目实现了一个简单的硬币找零问题的算法，并提供了相应的测试用例。通过动态规划算法，可以快速求解最少硬币数量的问题，具有较高的效率和准确性。

\end{document}
